﻿using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using Qas.CommonLogic;
using Qas.CommonLogic.BusinessObjects;

namespace Qas.CommonLogic.Business_Objects.Graph
{
    class BinaryHeap
    {
        private ArrayList heap;

        public BinaryHeap()
        {
            this.heap = new ArrayList();
        }

        public BinaryHeap(int capacity)
        {
            this.heap = new ArrayList(capacity);
        }

        /// <summary>
        /// Взятие корневого элемента-состояния кучи
        /// </summary>
        /// <returns></returns>
        public State Remove()
        {
            if (this.heap.Count > 0)
            {
                State resultState = this.heap[0] as State;
                this.heap[0] = this.heap[this.heap.Count-1];
                this.heap.RemoveAt(this.heap.Count - 1);
                this.Heapify(0);
                return resultState;
            }
            else
                return null;
        }
        
        /// <summary>
        /// Добавление состояния в кучу
        /// </summary>
        /// <param name="state"></param>
        public void Insert(State state)
        {
            //this.heapsize++;
            
            //heap.a[heapsize] = state;
            this.heap.Add(state);

            int index = this.heap.Count-1;
            
            this.Heapify(index);

            int parent = (index - 1) / 2;
            while ((index > 0) && ((this.heap[parent] as State).Weight > (this.heap[index] as State).Weight))
            {
                State tmpState = (State)this.heap[index];
                this.heap[index] = this.heap[parent];
                index = parent;
                this.heap[index] = tmpState;
                parent = (index - 1) / 2;
            }
            //heap[index] = state;
        }

        //// временный метод для тестирования
        ////

        //public void Insert(int state)
        //{
        //    //this.heapsize++;
        //    //heap.a[heapsize] = state;

        //    this.heap.Add(state);

        //    int index = this.heap.Count-1;
            
        //    this.Heapify(index);

        //    int parent = (index - 1) / 2;
        //    while ((index > 0) && ((Int32)this.heap[parent] < (Int32)this.heap[index]))
        //    {
        //        int tmp = (Int32)this.heap[index];
        //        this.heap[index] = this.heap[parent];
        //        index = parent;
        //        this.heap[index] = tmp;
        //        parent = (index - 1) / 2;
        //    }
        //}

        //public int Remove()
        //{
        //    if (this.heap.Count > 0)
        //    {
        //        int resultState = (Int32)this.heap[0];
        //        this.heap[0] = this.heap[this.heap.Count-1];
        //        this.heap.RemoveAt(this.heap.Count-1);
        //        this.Heapify(0);
        //        return resultState;
        //    }
        //    else
        //        return 0;
        //}
        //// конец временных методов
        ////

        /// <summary>
        /// Восстановление свойства кучи
        /// </summary>
        /// <param name="index"></param>
        private void Heapify(int index)
        {
            int left = index * 2;
            int right = index * 2 + 1;
            int minindex = index;

            ////// находим для данного элемент максимального предка
            ////if ((left <= this.heap.Count-1))
            ////    if ((Int32)this.heap[left] >
            ////        (Int32)this.heap[index])
            ////    {
            ////        maxindex = left;
            ////    }
            ////    else
            ////    {
            ////        maxindex = index;
            ////    }

            ////if ((right <= this.heap.Count-1))
            ////    if ((Int32)this.heap[right] >
            ////        (Int32)this.heap[index])
            ////    {
            ////        maxindex = right;
            ////    }


            // находим для данного элемент максимального предка
            if ((left <= this.heap.Count-1))
                if ((this.heap[left] as State).Weight <
                    (this.heap[index] as State).Weight)
                {
                    minindex = left;
                }
                else
                {
                    minindex = index;
                }

            if ((right <= this.heap.Count-1))
                if ((this.heap[right] as State).Weight <
                (this.heap[minindex] as State).Weight)
                {
                    minindex = right;
                }

            // поднимаем максимального предка наверх на 1 уровень
            if (minindex != index)
            {
                State tmp = (State)this.heap[index];
                this.heap[index] = this.heap[minindex];
                this.heap[minindex] = tmp;
                this.Heapify(minindex);
            }
        }
        
        //// Проверка на содержимость задачи
        //internal bool Contains(Task task)
        //{
        //    if (this.heap.Count == 0)
        //    {
        //        return true;
        //    }
        //    else
        //    {
        //        foreach (State state in this.heap)
        //        {
        //            if (state.Task.ID == task.ID)
        //            {
        //                return true;
        //            }
        //        }
        //        return false;
        //    }
        //}
        
        public State GetRoot()
        {
            if (this.heap.Count > 0)
            {
                State resultState = this.heap[0] as State;
                return resultState;
            }
            else
                return null;
        }

        public string ToString()
        {
            string res = String.Empty;
            for (int i = 0; i < this.heap.Count; i++)
            {
                res += ((Int32)this.heap[i] + " ");
            }
            return res;
        }

        #region ICollection Members

        public void CopyTo(Array array, int index)
        {
            throw new NotImplementedException();
        }

        public int Count
        {
            get
            {
                return this.heap.Count;
            }
        }


        #endregion

        #region IEnumerable Members

        public IEnumerator GetEnumerator()
        {
            throw new NotImplementedException();
        }

        #endregion

        internal List<State> getAll()
        {
            List<State> allStates = new List<State>();

            foreach (State state in this.heap)
            {
                allStates.Add(state);
            }
            return allStates;
        }
    }
}
